package com.janushuang.algorithm.sorter;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @author zhijing.huang
 *         Created by zhijing.huang on 2014/9/26.
 */
public class QuickSorter<E extends Comparable<E>> extends Sorter<E> {
    private static final Logger LOG = LoggerFactory.getLogger(QuickSorter.class);

    @Override
    public void sort(E[] data, int from, int len) {
        quickSort(data,from,from+len-1);
    }

    private void quickSort(E[] data, int from, int to) {
        if(to-from <1) return;
        
        int pivot = selectPivot(data,from,to);

        pivot = partition(data,from,to,pivot);

        quickSort(data,from,pivot-1);
        quickSort(data,pivot+1,to);
    }

    private int partition(E[] data, int from, int to, int pivot) {
        E temp = data[pivot];
        data[pivot] = data[to];

        while (from!=to) {
            while (from<to && data[from].compareTo(temp)<=0) {
                from++;
            }
            if (from < to) {
                data[to] = data[from];
                to--;
            }
            while (from<to && data[to].compareTo(temp)>=0) {
                to--;
            }
            if(from<to) {
                data[from] = data[to];
                from ++;
            }
        }
        data[from] = temp;
        return from;
    }

    private int selectPivot(E[] data, int from, int to) {
        return (from+to)/2;
    }

//    @Override
//    public void sort(int[] data) {
//        quickSort(data, 0, data.length - 1);
//    }
//
//    private void quickSort(int[] data, int i, int j) {
//        int pivotIndex = (i + j) / 2;
//        //swap
//        SortUtils.swap(data, pivotIndex, j);
//
//        int k = partition(data, i - 1, j, data[j]);
//        SortUtils.swap(data, k, j);
//        if ((k - i) > 1) quickSort(data, i, k - 1);
//        if ((j - k) > 1) quickSort(data, k + 1, j);
//    }
//
//    private int partition(int[] data, int l, int r, int pivot) {
//        do {
//            while (data[++l] < pivot) ;
//            while ((r != 0) && data[--r] > pivot) ;
//            SortUtils.swap(data, l, r);
//        }
//        while (l < r);
//        SortUtils.swap(data, l, r);
//        return l;
//    }
}
